15. 基数法则与组合数学初步

本节我们将聚焦计算各种有限集的基数，即集合内的元素数目。做到这一事情的底层思想是，依据双射法则，我们希望能够建立集合到集合的双射，或是集合到序列的双射，从而将对一个集合元素的计数转移到其它更加容易统计的元素的计数。

再搭配上一系列十分简单明了到我们一直就在自发使用它们的计数法则，就能够对许多常见的集合进行计数。例如：

加法法则：设 $A_{1}, A_{2}, \dots, A_{n}$ 为一系列 不相交 集合，则
$| ⋃_{i = 1}^{n} A_{i} | = \sum_{i = 1}^{n} | A_{i} |$

乘法法则：设 $P_{1}, P_{2}, \dots, P_{n}$ 为任意集合列，则
$| \prod_{i = 1}^{n} P_{i} | = \prod_{i = 1}^{n} | P_{i} |$
式中的“乘法”为笛卡尔积。

$n$ 位仅由数字组成的 PIN 码共有 $10^{n}$ 个。此外，乘法法则解释了特定长度的二进制串的个数。我们设 $B = {0, 1}$ ，显然长度为 $n$ 的二进制串可以表示为 $B^{n}$ ，依据乘法法则， $| B^{n} | = 2^{n}$ 。

乘法法则可以借助双射法则在序列上重新阐述：

广义乘法法则：设 $S$ 是许多长度为 $k$ 的序列构成的集合，且对这些序列满足

序列第一项有 $n_{1}$ 种选择；

对每一个第一项，第二项有 $n_{2}$ 种选择；
......
以此类推，则

$| S | = \prod_{i = 1}^{k} n_{i}$

广义乘法法则坚定了我们一个进行集合基数的方法：将集合计数映射到序列计数上。

我们称集合 $S$ 的一个 排列（Permutation） 是一个 $S$ 中所有元素出现一次且仅一次的序列，依据广义乘法法则，具有 $n$ 个元素的集合共有 $n!$ 个排列。阶乘函数也将在本节的后续内容中大量出现。

我们继续介绍另一个十分重要的计数法则：

除法法则：设 $f$ 是一个 $A \to B$ 的 全函数，若 $f$ 是 $k$ 对一的，则
$| A | = k | B |$

除法法则在我们使用映射将对 $A$ 的计数转移到对 $B$ 的计数，但发现 $A$ 中每个元素都映射到 $k$ 个 $B$ 中元素时，用于修正重复计数的问题。

例如，考虑下面的问题：我们要将 $n$ 个人安排到圆桌上就坐。对各种不同的排座方法，若从某一个特定的人开始，顺时针转一圈得到相同的人物就坐序列，则我们称它们为同一种 安排（Arrangement）。如果我们固定开始排座的位置，显然我们能得到共有 $n!$ 种排座方法。对于排座方法，我们令所有人移动到顺时针方向的下一把椅子就坐，显然能够发现排座对安排是 $n$ 对一的，依据乘法法则，对 $n$ 个人的圆桌排座问题共有 $(n - 1)!$ 中安排。

还有一个基本问题：一个 $n$ 元素集合 $S$ 有多少个 $k$ 元素子集？我们考虑 $S$ 的一个排列，取其前 $k$ 个元素组成我们想要的子集。显然，在该排列中，前 $k$ 个元素的排列顺序与后 $(n - k)$ 个元素的排列顺序无关紧要，因此集合的排列到其 $k$ 元素自己是 $k! (n - k)!$ 对一的，应用乘法法则，我们得到

子集法则：一个 $n$ 元素集合的不同的 $k$ 元素子集的数量为
$\frac{n!}{k! (n - k)!}$
我们称其为 组合数，又称 二项式系数，记为 $(\binom{n}{k})$ ，又可记作 $C_{n}^{k}$ 。

了解了许多计数规则，我们来尝试应用一下吧！

例题

给定一副标准的扑克牌（不含大小王），任意抽出五张，有多少种符合“两对”^[1]牌型的手牌？

错误做法

考虑构造一个六个元素的序列，分别代表第一个对子的点数、花色；第二个对子的点数、花色；单张的点数、花色。显然：

第一个对子的点数有 $13$ 种选择；
第一个对子的花色有 $(\binom{4}{2})$ 种选择；
第二个对子的点数有 $12$ 种选择；
第二个对子的花色有 $(\binom{4}{2})$ 种选择；
单张的点数有 $11$ 种选择；
单张的花色有 $4$ 种选择。
故答案为

13 \times 12 \times 11 \times {(\binom{4}{2})}^{2} \times 4

但这个答案不对，它错在哪里？

正解

考虑如下两个序列： $(3, {♠, ♣}, K, {♡, ♢}, 7, ♣)$ ， $(K, {♡, ♢}, 3, {♠, ♣}, 7, ♣)$ 。容易发现它们其实对应着同一幅手牌，这表明错解给出的映射是 二对一 的。应用除法法则可得到正确答案

\frac{13 \times 12 \times 11 \times {(\binom{4}{2})}^{2} \times 4}{2}

有两个好办法可以避免上面的例题中可能会犯的重复计数错误：

对建立的映射多留点心眼，回头检查一下建立的映射是否真的是双射，如果不是，应用除法法则修正一下重复计数的问题。
用不同的方法再解决一边问题，只要两个方法都是正确的，那么结果也应该相同。

我们回顾一下组合数的引入过程，选出一个子集事实上是将集合分割为了两部分，因此我们自然会考虑将子集作多次分割共有多少种方案。形式化地，我们设 $A$ 是一个 $n$ 元素集合， $A_{1}, A_{2}, \dots, A_{k}$ 是 $A$ 的一个划分，且 $| A_{i} | = c_{i}$ 。称 $A$
的一个 $(c_{1}, c_{2}, \dots, c_{k})$ 分割为序列 $(A_{1}, A_{2}, \dots, A_{k})$ 。仿照得出组合数的方法，我们有

一个 $n$ 元素集合的 $(c_{1}, c_{2}, \dots, c_{k})$ 分割数目为
$(\binom{n}{c_{1}, c_{2}, \dots, c_{k}}) = \frac{n!}{\prod_{i = 1}^{k} c_{i}!}$
其中 $(\binom{n}{c_{1}, c_{2}, \dots, c_{k}})$ 称作 多项式系数。

前面提到的排列计数都建立在元素各异的情况下。接下来我们考虑存在相同元素时排列的总数：给定元素序列 $(e_{1}, e_{2}, \dots, e_{n})$ ，每个元素需在排列中出现次数的序列 $(k_{1}, k_{2}, \dots, k_{n})$ ，设 $N = \sum_{i = 1}^{n} k_{i}$ 。共有多少种排列？

我们使用子集分割的思想，考虑一个位置集合 ${1, 2, 3, \dots, n}$ ，将排列转化为对该集合作分割，并顺序给各个元素分配一个子集，因此我们得到

多重集和的排列：给定元素序列 $(e_{1}, e_{2}, \dots, e_{n})$ ，每个元素需在排列中出现次数的序列 $(k_{1}, k_{2}, \dots, k_{n})$ ，其对应的排列个数为
$(\binom{\sum_{i = 1}^{n} k_{i}}{k_{1}, k_{2}, \dots, k_{n}})$

这种组合的思想容易联想到代数中加法对乘法的分配律，因此我们来考虑一下代数与组合数学中至关重要的定理：

二项式定理：对任意 $a, b$ 与 $n \in N$
$(a + b)^{n} = \sum_{k = 0}^{n} (\binom{n}{k}) a^{n - k} b^{k}$

这个公式的来源可以简单说明如下：我们不妨考虑 $(1 + x)^{n}$ ，考虑多项式乘法的过程，我们知道其完全展开会产生 $2^{n}$ 项，每一项为顺次从 $n$ 个 $(1 + x)$ 中选择 $1$ 还是 $n$ 相乘后的结果，这些项相加结果为一个 $n$ 次多项式。因此对于其中的 $k$ 次系数 $c_{k}$ ，其应为在 $n$ 个 $(1 + x)$ 中选择了 $k$ 个 $x$ 与 $(n - k)$ 个 $1$ ，因此这一项的系数就为 $(\binom{n}{k})$ 。

通过应用上面提到过的多重集合的排列，我们很容易将二项式定理推广到多项式定理：

多项式定理：对任意 $x_{1}, x_{2}, \dots, x_{n}$ 与 $n \in N$
${(\sum_{i = 1}^{n} x_{i})}^{n} = \sum_{\begin{matrix} k_{1}, k_{2}, \dots, k_{m} \in N \\ k_{1} + k_{2} + \dots + k_{m} = n \end{matrix}} (\binom{n}{k_{1}, k_{2}, \dots, k_{m}}) \prod_{i = 1}^{m} x_{i}^{k_{i}}$

鸽巢原理 同样是一个十分显然以至于我们一直在无意使用的计数原理案例：

鸽巢原理：如果鸽子的数量比鸽巢的数量多，则把所有鸽子放进鸽巢后必然有至少两只鸽子在一个巢中。形式化地来说，设 $f$ 是一个 $A \to B$ 的 全函数，若 $| A | > | B |$ ，则 $A$ 中至少有两个元素映射到 $B$ 中同一个元素上。

鸽巢原理的逆否命题同样成立，其内容为，若 $| A | > | B |$ ，则不存在 $A \to B$ 的满射。

鸽巢原理可以自然推广：

广义鸽巢原理：若将 $n$ 只鸽子放进 $k$ 个鸽巢中，则必有一个鸽巢内至少有 $⌈ \frac{n}{k} ⌉$ 个鸽子。形式化地来说，若 $f$ 是一个 $A \to B$ 的 全函数，则 $A$ 中至少有 $⌈ \frac{| A |}{| B |} ⌉$ 个元素映射到 $B$ 中同一个元素上。

应用鸽巢原理可以用于判定某些计数问题的下限。应用鸽巢原理时，务必搞清鸽子、鸽巢分别对应哪个集合，以及将鸽子分配到鸽巢的方法。

加法法则使用的条件是各集合两两不交，对于存在并集的集合，我们可以使用 容斥原理 来处理。容斥原理是加法法则的直接推广，其内容为：

两个集合的容斥原理：对任意有限集 $A, B$
$| A \cup B | = | A | + | B | - | A \cap B |$

基于两个集合的容斥原理，可以自然推广到三个集合的情况：

三个集合的容斥原理：对任意有限集 $A, B, C$
$\begin{aligned} | A \cup B \cup C | = & | A | + | B | + | C | \\ - | A \cap B | - | B \cap C | - | A \cap C | \\ + | A \cap B \cap C | \end{aligned}$

对该公式的理解可以画出三个集合的 Venn 图后按照与两个集合的容斥原理类似的方式进行。或者令 $B = B \cup C$ 代入两个集合的容斥原理验证。

一路推广下去，我们可以得到对任意数量集合的容斥原理：

容斥原理：对 $n$ 个任意有限集 $S_{1}, S_{2}, \dots, S_{n}$
$| ⋃_{i = 1}^{n} S_{i} | = \sum_{\emptyset \neq I \subseteq {1, 2, \dots, n}} (- 1)^{| I | + 1} | ⋂_{i \in I} S_{i} |$
直观解释就是， $n$ 个集合交集的大小等于：

单个集合的基数之和

减去所有两个集合的并集的基数之和

加上所有三个集合的并集的基数之和

减去所有四个集合的并集的基数之和
......

应用容斥原理，我们就可以给出关于欧拉函数展开式的另一种证明：

欧拉函数展开式的另一证明

我们设 $S$ 是所有 $[0, n)$ 中不与 $n$ 互质的整数组成的集合。显然 $ϕ (n) = n - | S |$ 。我们考虑如何求出 $S$ 。

设 $C_{a}$ 代表所有 $[0, n)$ 中所有能被 $a$ 整除的整数组成的集合。对于 $n$ 的唯一分解序列 $p_{1}^{α_{1}} p_{2}^{α_{2}} \dots p_{n}^{α_{n}}$ ，容易知道

S = ⋃_{p ∣ n} C_{p}

对该式子应用容斥原理即可。在此之前我们先考虑如何求出容斥原理需要的多个 $C_{p}$ 的并集的大小。依据质数的性质，对于并集 $C_{p} \cap C_{q}$ ，其只含有 $p q$ 的正整数倍倍数，在 $[0, n)$ 中满足这一条件的整数数量显然为 $⌊ \frac{n}{p q} ⌋$ ，自然推广到任意数量集合的并集，有

| ⋂_{p \in {p_{1}, p_{2}, \dots, p_{n}}} C_{p} | = \frac{n}{\prod_{p \in {p_{1}, p_{2}, \dots, p_{n}}} p}

接着应用容斥原理

\begin{aligned} | S | = & | ⋃_{p ∣ n} C_{p} | \\ = & \sum_{\emptyset \neq I \subseteq {1, 2, \dots, m}} (- 1)^{| I | + 1} | ⋂_{i \in I} C_{p_{i}} | \\ = & \sum_{\emptyset \neq I \subseteq {1, 2, \dots, m}} (- 1)^{| I | + 1} \frac{n}{\prod_{i \in I} p_{i}} \\ = & - n \sum_{\emptyset \neq I \subseteq {1, 2, \dots, m}} \frac{1}{\prod_{i \in I} - p_{i}} \\ = & - n (\prod_{i = 1}^{m} (1 - \frac{1}{p_{i}})) + n \end{aligned}

代入 $ϕ (n) = n - | S |$ 即可证明。

我们前面提到过可以用多种思路解决同一道计数问题。由于不同思路给出的式子通常不同，我们可以进一步利用来导出一系列十分有用的式子，例如：

帕斯卡三角恒等式*：$${n \choose k} = {n-1 \choose k-1} + {n-1 \choose k}$$
$(\binom{n}{k}) = (\binom{n - k}{k})$

证明

考虑经典的 $n$ 选 $k$ 问题，我们知道它的答案是 $(\binom{n}{k})$ 。接下来我们换一种思路，考察某个具体的元素 $s$ ：

若 $s$ 在选定的子集中，则选剩余 $k - 1$ 个元素的方案是 $(\binom{n - 1}{k - 1})$ 。
若 $s$ 不在选定的子集中，则选剩余 $k$ 个元素的方案是 $(\binom{n - 1}{k})$ 。

两种方案显然互斥，依据加法原理，可以得到上面的结论。

这种依据计数原理得到代数事实的方法称作 组合证明，其能够在不基于繁琐代数运算的情况下给出对某些式子的证明，其基本框架为：

定义一个集合 $S$ ；
通过一种计数方式给出 $| S | = P$ ；
通过另一种计数方式给出 $| S | = Q$ ；
得出结论： $P = Q$ 。

构建组合证明的关键为选择合适的 $S$ ，通常依据公式中较为简单的一侧确定。

两对是满足五张牌中有两对相同点数的牌的牌型。 ↩︎